package com.cqs.leetcode.recursion;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

/**
 * @author lixqw
 * @date 2020/8/16
 */
public class PermutationLCCI {



    /**
     * 不重复的元素的全排列
     *
     * @param S
     * @return
     */
    public String[] permutation(String S) {
        byte[] used = new byte[S.length()];
        char[] tmp = new char[S.length()];
        List<String> list = new ArrayList<>();
        permutation(S, used, tmp, 0,list);
        String[] arr = new String[list.size()];
        list.toArray(arr);
        return arr;
    }

    private void permutation(String s, byte[] used, char[] chars, int level,List<String> result) {
        //递归出口
        if (level == s.length()){
            result.add(new String(chars));
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (used[i] == 1) continue;
            chars[level] = s.charAt(i);
            //标记字符已经使用
            used[i] = 1;
            permutation(s, used, chars, level + 1,result);
            //回溯
            used[i] = 0;
        }
    }

    public static void main(String[] args) {

        List<String> tests = Lists.newArrayList("a","abcde");
        for (String test : tests) {
            PermutationLCCI lcci = new PermutationLCCI();
            String[] permutation = lcci.permutation(test);
            System.out.println(test + "\t" + Lists.newArrayList(permutation));
        }

    }
}
